import abc
import random
from typing import Union


class DataSet:
    """
    数据集类，为了和 sklearn 一致。
    """

    def __init__(self, data, target) -> None:
        """
        构造方法。

        :param data: 属性数据集
        :param target: 标签数据集
        """
        # 属性数据集 成员属性
        self.data = data
        # 标签数据集 成员属性
        self.target = target


def load_iris() -> DataSet:
    """
    读取 鸢尾花 数据集。

    这里简单实现读取本地的数据集。

    :return: 鸢尾花数据集
    """
    # 数据列表
    data_list = []

    # 读取 文件
    with open('iris_training.csv', mode='r') as f:
        # 每行数据。这里采用逐行读取，为的是如果读取超大文本不会造成耗尽内存
        datum_string = f.readline()

        # 直至读取不到数据即结束
        while datum_string:
            # 将读取到的行数据通过 split 方法分割开，并存在 datum_split 列表中
            datum_split = datum_string.split(',')
            # datum_split 列表中的元素都是 字符串类型，所以需要将其转换为 浮点数类型
            datum = [float(x) for x in datum_split]
            # 将处理好的数据添加至 数据列表中
            data_list.append(datum)
            # 继续读取下一行
            datum_string = f.readline()

    # 将数据库列表中的数据中的元素分为属性和标签，其中最后一个是标签，其余都是属性
    data = [datum[:-1] for datum in data_list]
    target = [datum[-1] for datum in data_list]

    # 包转成 数据集类型 后返回
    return DataSet(data, target)


def train_test_split(X: list, y: list, *, train_size: float, random_state: Union[int, float]) -> tuple:
    """
    分离训练集和测试集。
    
    :param X: 属性数据集
    :param y: 标签数据集
    :param train_size: 训练集比率。测试集比率 = 1 -  训练集比率
    :param random_state: 随机数种子。必须要有该参数，因为如果没有的话，无法保证每次随机产生的数据是一致的。
    :return: 训练属性数据集，测试属性数据集，训练标签数据集，测试标签数据集，
    """
    if len(X) != len(y):
        raise ValueError('X 和 y 的长度必须一致。')

    # 初始化随机发生器种子，保证每次随机产生的数据是一致的。
    random.seed(random_state)

    # region 将属性和标签合并为元组，以便乱序
    X_y = []
    for i in range(len(X)):
        X_y.append((X[i], y[i]))
    # endregion 将属性和标签合并，以便乱序

    # 乱序 属性和标签 的列表
    random.shuffle(X_y)

    # 将乱序好的 属性和标签 分离，以便分割出 训练集和测试集
    X = [X_y_item[0] for X_y_item in X_y]
    y = [X_y_item[1] for X_y_item in X_y]

    # 计算 训练集数量
    train_count = int(len(X) * train_size)

    # 切片分割训练集和测试集
    X_train, X_test = X[:train_count], X[train_count:]
    y_train, y_test = y[:train_count], y[train_count:]

    return X_train, X_test, y_train, y_test


class MyKNeighborsClassifier:
    """
    这是一个抽象类，它本身并没有实现 KNN 算法，它只是定义了 KNN 算法所需的接口。

    子类需继承该类并实现其方法以完成一个具体的 KNN 算法。
    """

    def __init__(self, n_neighbors=5) -> None:
        """
        本类的构造方法。

        其中只包含了一个 n_neighbors 参数。我们只实现简单的 KNN 分类器，不涉及到其他的参数，如距离函数参数，距离权重参数等。

        :param n_neighbors: 邻居数，默认为 5。该参数表示取多少个邻居来比较类别。
                            如 5 个邻居，则将目标最近的 5 个邻居点列出，比较邻居点中哪种类别的最多，则认为目标点属于该种类别
        """
        # 邻居数。该参数表示取多少个邻居来比较类别。如 5 个邻居，则将目标最近的 5 个邻居点取出，比较邻居点中哪种类别的最多，则认为目标点属于该种类别
        self._n_neighbors = n_neighbors

        # 分类器是否生成标识。用于标记是否训练好分类器。该成员属性会被使用至 predict 方法，在 predict 之前，我们需保证分类器已被训练好
        self._fitted = False

    def fit(self, X_train: list, y_train: list) -> None:
        """
        通过分析训练数据集训练好分类器。

        :param X_train: 训练属性数据集
        :param y_train: 训练标签数据集
        :return: None
        """
        # 训练属性数据集 成员属性
        self._X_train = X_train

        # 训练属性数据集 成员属性
        self._y_train = y_train

        # 调用抽象方法 _implemented_fit。子类实现 _implemented_fit 方法后，这里就将调用子类的 具体方法 _implemented_fit
        self._implemented_fit(X_train, y_train)

        # 既然已经调用了 _implemented_fit，则 分类器是否生成标识 置为 True
        self._fitted = True

    @abc.abstractmethod
    def _implemented_fit(self, X_train: list, y_train: list) -> None:
        """
        通过分析训练数据集训练好分类器。

        该方法为抽象方法，子类需实现该方法。
        该方法是 protected 访问权限，即只能被子类实现。

        该方法会被 fit 调用。

        为何不直接将 fit 设计成抽象方法？

        这么设计的原因是因为如果将 fit 设计为抽象方法，则每个子类的 fit 方法都需要去实现以下 3 行代码。

        self._X_train = X_train

        self._y_train = y_train

        self._fitted = True

        :param X_train: 训练属性数据集
        :param y_train: 训练标签数据集
        :return: None
        """
        pass

    def predict(self, X_test: list) -> list:
        """
        通过给出的测试属性数据集 预测 测试集标签。

        调用该方法前，必须先调用 fit 方法。

        :param X_test: 测试属性数据集
        :return: 预测的测试集标签列表
        """
        if not self._fitted:
            raise Exception('调用 predict 方法前请先调用 fit 方法。')
        return self._implemented_predict(X_test)

    @abc.abstractmethod
    def _implemented_predict(self, X_test: list) -> list:
        """
        通过给出的测试属性数据集 预测 测试集标签。

        该方法为抽象方法，子类需实现该方法。
        该方法是 protected 访问权限，即只能被子类实现。

        该方法会被 predict 调用。
        为何不直接将 predict 设计成抽象方法？
        这么设计的原因是因为如果将 predict 设计为抽象方法，则每个子类的 predict 方法都需要去实现检测 fit 方法是否被调用。

        :param X_test: 测试属性数据集
        :return: 预测的测试集标签列表
        """
        pass


class SimpleMyKNeighborsClassifier(MyKNeighborsClassifier):
    """
    简单 KNN 算法。

    该类继承至 MyKNeighborsClassifier，是 MyKNeighborsClassifier 的一个具体实现。

    该类完成了一个初级的实现，实现方式非常简单，采用了循环求距离的方式，所以时间复杂度很高。
    """

    def __init__(self, n_neighbors=5) -> None:
        """
        本类的构造方法。

        :param n_neighbors:
        """
        # 由于继承至 MyKNeighborsClassifier，所以需调用父类的构造函数
        super().__init__(n_neighbors)

    def _implemented_fit(self, X_train, y_train) -> None:
        """
        实现了父类的 _implemented_fit 抽象方法。

        本类采用了循环求距离的方式，不需要生成分类器，所以只有 pass 语句

        :param X_train: 训练属性数据集
        :param y_train: 训练标签数据集
        :return: None
        """
        pass

    def _implemented_predict(self, X_test: list) -> list:
        """
        实现了父类的 _implemented_predict 抽象方法。

        采用循环遍历 测试属性数据集，对每个 测试属性数据集 做出预测

        :param X_test: 测试属性数据集
        :return: 预测的测试集标签列表
        """
        # 结果列表。最后要返回的 预测的测试集标签列表
        y = []

        # 通过 for 循环的方式遍历 测试属性数据集
        for i, x in enumerate(X_test):
            # 将每个预测到的结果添加至 结果列表 里
            y.append(self.__classify(x))

        return y

    def __classify(self, x):
        """
        对单个数据进行预测。

        :param x: 单个数据的 属性数据集
        :return: 该属性数据集 所预测到的 标签
        """
        # 训练数据集中每个数据在训练集中的位置 和 单个数据与该数据的距离 组成的元组 的列表。
        # 之所以要记录 在训练集中的位置，是因为待会需要把 该列表内的元素按照距离排序，如不记录，排序后 在训练集中的位置 信息将丢失
        # 造成无法知道 该数据所对应的 y_train 中的标签
        X_train_position_and_distance = []

        # 计算 单个数据与训练数据集中每个数据的距离
        for position, x_train_item in enumerate(self._X_train):
            # 单个数据与训练集的数据的欧氏距离。计算 单个数据与训练集的数据的欧氏距离
            euclidean_distance = SimpleMyKNeighborsClassifier.__euclidean_distance(x, x_train_item)
            # 将 训练集数据的 在训练集中的位置 和 单个数据与该数据的距离 打包成元组
            item = (position, euclidean_distance)
            # 将元组添加至 列表。
            X_train_position_and_distance.append(item)

        # 对 在训练集中的位置和距离元组列表 按距离进行升序排序
        X_train_position_and_distance = sorted(X_train_position_and_distance, key=lambda dp: dp[1])

        # region 下面计算在一定邻居数内，哪种类别的邻居最多

        # 类别和数量的映射
        category_map_counting = {}

        # 循环取出离的最近的 _n_neighbors 个邻居的 在训练集中的位置和距离元组
        for i in range(self._n_neighbors):
            # 邻居在训练集中的位置和距离元组
            X_train_position_and_distance_item = X_train_position_and_distance[i]

            # 邻居在训练集中的位置
            X_train_position = X_train_position_and_distance_item[0]

            # 邻居的类别。通过 邻居在训练集中的位置 找到邻居的类别
            category = self._y_train[X_train_position]
            # 如果该类别的数量没有定义，则将其设定为 0
            if category_map_counting.get(category) is None:
                category_map_counting[category] = 0
            # 该类别的数量 +1
            category_map_counting[category] += 1

        # 找出最多数量的类别
        # 最多数量的类别          当前最多的数量
        max_counting_category, max_counting = 0, 0
        # 循环每个类别和其数量，找出最多的那一个
        for category in category_map_counting:
            # 如果 当前最多的数量 小于 该类别的数量，则该类别设为最多数量的类别，当前最多的数量 改为 该类别的数量
            if max_counting < category_map_counting[category]:
                max_counting_category, max_counting = category, category_map_counting[category]
        # endregion 下面计算在一定邻居数内，哪种类别的邻居最多

        return max_counting_category

    @staticmethod
    def __euclidean_distance(point1: list, point2: list):
        """
        求两点之间的欧氏距离

        :param point1: 点 1 坐标
        :param point2: 点 2 坐标
        :return: 两点之间的欧氏距离
        """
        if len(point1) != len(point2):
            raise ValueError('x1 和 x2 长度必须一致。')

        # 不同坐标轴之间差的平方的和
        _sum = 0

        # 循环求 坐标轴之间差的平方
        for i in range(len(point1)):
            # 将 坐标轴之间差的平方 相加
            _sum += (point1[i] - point2[i]) ** 2

        # 求平方根得到两点间的欧氏距离
        return _sum ** 0.5
